package baseclass.h_heap;

import java.util.*;

/**
 * 求TopK。维护一个小跟堆，当数据流比堆顶还大，用该数替换堆顶。
 *
 * 优势：无论数据流多么大，额外空间就是O(K)。
 * 时间复杂度O(NlogK)
 * @date 2020/2/29 21:46
 */
public class TopK {
    private static Queue<Integer> minQ;
    private final int CAPACITY;
    public TopK(int k) {
        this.minQ = new PriorityQueue<>();
        this.CAPACITY = k;
    }
    public void insert(int e){
        if(minQ.size() < CAPACITY){
            minQ.add(e);
            return;
        }
        if(minQ.peek() < e){
            minQ.poll();
            minQ.add(e);
        }
    }
    public Integer[] getTopK(){
        List<Integer> res = new LinkedList<>();
        Iterator<Integer> iterator = minQ.iterator();
        while (iterator.hasNext()){
            res.add(iterator.next());
        }
        return res.toArray(new Integer[0]);

    }

    public static void main(String[] args) {
        float a = -1.1f;
        System.out.println(a);
        Integer.valueOf("");
        int c = 100_999;
    }
}
